package leetcode_700;

/**
 *@author 周杨
 *KthSmallestNumberInMultiplicationTable_668 找出乘法表里最小的k个数
 *describe:直接二分查找 AC 80%
 *2018年9月29日 下午2:00:42
 */
public class KthSmallestNumberInMultiplicationTable_668 {
	
	    public int findKthNumber(int m, int n, int k) {
	    	int lo = 1, hi = m*n, mid = -1;
	    	while(lo < hi) {			// 注意这里要变化
	    		mid = lo+(hi-lo)/2;
	    		int t = getNotLarger(m, n, mid);
	    		if(t == k)		hi = mid;	// 等于还要往左走到乘法表里面有的（不是往右走，不然就是k+1）
	    		else if(t > k)	hi = mid;	// 因为乘法表里面有重复的数，比如mid有多个，结果仍然可能是mid
	    		else			lo = mid+1;
	    	}
	    	return lo;
	    }
	 
		private int getNotLarger(int m, int n, int mid) {
			int cnt = 0;
			for(int i=1; i<=m; i++)	
				cnt += Math.min(mid/i, n);
			return cnt;
		}
	

}
